//逆波兰表达式

#ifndef __CALC_H_
#define __CALC_H_

#include "stack.h"
#include "queue.h"


//判断字符是否为数字
int charIsNumber(char value)
{
    int i;
    char *numberString = "0123456789";
    for(i=0;i<10;i++)
    {
        if(value == numberString[i])
        {
            return 1;
        }
    }
    return 0;
}

//判断字符是否为运算符
int charIsOperator(char value)
{
    int i;
    char *operatorString = "+-*/()";
    for(i=0;i<6;i++)
    {
        if(operatorString[i] == value)
        {
            return 1;
        }
    }
    return 0;
}

//计算简单的加减乘除
int getResult(int num1,int num2,int operator)
{
    int result;
    if(operator == '+')
    {
        result = num1 + num2;
    }
    else if(operator == '-')
    {
        result = num1 - num2;
    }
    else if(operator == '*')
    {
        result = num1 * num2;
    }
    else if(operator == '/')
    {
        result = num1 / num2;
    }
    return result;
}

//字符运算表达式用队列表示
void stringToQueue(char *expression,int len, queue *q)
{
    int i;
    int operator,number;
    for(i=0;i<len;i++)
    {
        if(charIsOperator(expression[i]))
        {
            operator = expression[i];
            queuePush(q,operator,1);
        }
        else if(charIsNumber(expression[i]))
        {
            number = expression[i]-'0';
            while(charIsNumber(expression[++i]) && i<len)
            {
                number = number*10 + (expression[i]-'0');
            }
            queuePush(q,number,0);
            i--;
        }
    }
}

//判断运算符优先级
int rank(int operator)
{
    if(operator == '+' || operator == '-')
    {
        return 1;
    }
    else if(operator == '*' || operator == '/')
    {
        return 2;
    }
    else
    {
        return 0;
    }
}

//operator优先级高返回TRUE，优先级高，入运算符栈，否则出栈
int priority(int operator,int stackOperator)
{
    if(rank(operator) > rank(stackOperator))
    {
        return 1;
    }
    return 0;
}

//获取后缀表达式
int getRpnList(queue *inputQueue,queue *outputQueue)
{
    int value,type=-1;//队内元素和元素类型,0数字，1运算符
    int operator;//栈中的运算符
    stack operatorStack;//操作符栈
    stackInit(&operatorStack);//一定要初始化，否则栈不为空。
    while(!queueIsEmpty(inputQueue))
    {
        queuePop(inputQueue, &value, &type);
        if(type == 1)//value为运算符符
        {
            if(value == '(')
            {
                stackPush(&operatorStack, value);
            }
            else if(value == ')')
            {
                if( !stackIsEmpty(&operatorStack) )
                {
                    stackPop(&operatorStack,&operator);
                    while(operator != '(' && !stackIsEmpty(&operatorStack) )
                    {
                        queuePush(outputQueue, operator,1);
                        stackPop(&operatorStack,&operator);
                    }
                }
                if(operator != '(')//栈已空且栈底元素不为(
                {
                    printf("()unmatched");
                    return 0;
                }
            }
            else// + - * /
            {
                if( !stackIsEmpty(&operatorStack) )
                {
                    peek(&operatorStack,&operator);
                    while( !priority(value, operator) && !stackIsEmpty(&operatorStack) )
                    {
                        stackPop(&operatorStack,&operator);
                        queuePush(outputQueue, operator,1);
                        peek(&operatorStack,&operator);
                    }
                }
                stackPush(&operatorStack,value);
            }
        }
        else if(type == 0)//数字直接入队列
        {
            queuePush(outputQueue, value, 0);
        }
    }
    
    while(!stackIsEmpty(&operatorStack))
    {
        stackPop(&operatorStack,&operator);
        if(operator == '(')
        {
            printf("error: ( unmatched");
            return 0;
        }
        queuePush(outputQueue, operator,1);
    }
    return 1;
}


int solveRpnList(queue *rpnList,int *expIsTrue)
{
    int value,type=-1;
    int prev,next;
    stack solveStack;
    stackInit(&solveStack);
    while(!queueIsEmpty(rpnList))
    {
        queuePop(rpnList,&value,&type);
        if(type == 0)
        {
            stackPush(&solveStack,value);
        }
        else if(type == 1)
        {
            if(solveStack.top < 1)//栈元素少于2个
            {
                printf("表达式有误\n");
                *expIsTrue = 0;
                return 0;
            }
            stackPop(&solveStack,&next);
            stackPop(&solveStack,&prev);
            stackPush(&solveStack,getResult(prev,next,value));
        }
    }
    
    if(solveStack.top!=0)
    {
        printf("表达式有误\n");
        *expIsTrue = 0;
        return 0;
    }
    else
    {
        *expIsTrue = 1;
        return solveStack.data[0];
    }
}

void printResult(int result,int expIsTrue)
{
    if(expIsTrue == 1)
    {
        printf("%d",result);
    }
    else if(expIsTrue == 0)
    {
        printf("ERROR");
    }
}

#endif


